package leetcode_101_120;

import utils.ListNode;
import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class sortedListToBST_109 {
    /**
     * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
     */
    public TreeNode sortedListToBST(ListNode head) {
        /**
         * 按上一题的思路思路即可
         * 1ms
         */
        if(head==null)
            return null;
        TreeNode node = new TreeNode();
        List<Integer>nums=new ArrayList<>();
        while(head!=null){
            nums.add(head.val);
            head=head.next;
        }

        dfs(node, nums, 0, nums.size() - 1, 0);
        return node;
    }
    /**
     * 递归构造高度平衡二叉树
     * @param node  当前二叉树的根节点
     * @param nums  二叉搜索树的数组
     * @param left  数组左右边界
     * @param right
     * @param flag  判定左右子树，0左，1右
     */
    void dfs(TreeNode node, List<Integer> nums, int left, int right, int flag) {
        int mid = left + (right - left) / 2;
        if (right - left == 1 && flag == 0) {  //如果只剩两个数字，并且是在处理左子树，上面的计算默认根节点偏左
            mid++; // 需要使根节点靠右，达到大于左子树的目的
        }
        node.val = nums.get(mid);

        if (left == right)
            return;

        if (mid != left) {
            node.left = new TreeNode();
            dfs(node.left, nums, left, mid - 1, 0);
        }
        if (mid != right) {
            node.right = new TreeNode();
            dfs(node.right, nums, mid + 1, right, 1);
        }
    }
}
